#ifndef DP_H_
#define DP_H_

#include <algorithm>
#include <execution>
#include <numeric>
#include <string>
#include <vector>

namespace lxj
{
// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)
// 测试链接 : https://leetcode.cn/problems/fibonacci-number/
// 注意：最优解来自矩阵快速幂，时间复杂度可以做到O(log n)
// 此递归版
inline long long fibonacci(int n)
{
    if (n == 0) return 0ll;
    if (n == 1) return 1ll;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// 记忆化版
inline long long fibonacci2(int n)
{
    int       a = 0, b = 1;
    long long ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = a + b;
        a   = b;
        b   = ans;
    }
    return ans = n == 1 ? 1 : ans;
}

// 最低票价
// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行
// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出
// 每一项是一个从 1 到 365 的整数
// 火车票有 三种不同的销售方式
// 一张 为期1天 的通行证售价为 costs[0] 美元
// 一张 为期7天 的通行证售价为 costs[1] 美元
// 一张 为期30天 的通行证售价为 costs[2] 美元
// 通行证允许数天无限制的旅行
// 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证
// 那么我们可以连着旅行 7 天(第2~8天)
// 返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费
// 测试链接 : https://leetcode.cn/problems/minimum-cost-for-tickets/
class MinimumCostForTickets {
    inline static constexpr int duration[] = {1, 7, 30};

    inline int f1(const std::vector<int>& days, const std::vector<int>& costs, int i)
    {
        if (i == days.size()) return 0;

        int ans = ~(1 << 31);
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.size() && days[i] + duration[k] > days[j]) j++;
            ans = std::min(ans, costs[k] + f1(days, costs, j));
        }
        return ans;
    }

    inline int f2(std::vector<int>& days, std::vector<int>& costs, int i, int* dp)
    {
        if (i == days.size()) return 0;
        if (dp[i] != 0) return dp[i];
        int ans = ~(1 << 31);
        for (int k = 0, j = i; k < 3; k++) {
            while (j < days.size() && days[i] + duration[k] > days[j]) j++;
            ans = std::min(ans, costs[k] + f2(days, costs, j, dp));
        }
        dp[i] = ans;
        return ans;
    }

public:
    // 暴力递归版
    inline int mincostTickets1(std::vector<int>& days, std::vector<int>& costs)
    {
        return f1(days, costs, 0);
    }

    // 记忆化递归版
    inline int mincostTickets2(std::vector<int>& days, std::vector<int>& costs)
    {
        int* dp  = new int[days.size()]{0};
        int  ans = f2(days, costs, 0, dp);
        delete[] dp;
        return ans;
    }

    // 严格位置依赖的动态规划
    // 从底到顶的动态规划
    inline int mincostTickets3(std::vector<int>& days, std::vector<int>& costs)
    {
        int              n = days.size();
        std::vector<int> dp(366, ~(1 << 31));
        dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int k = 0, j = i; k < 3; k++) {
                while (j < n && days[i] + duration[k] > days[j]) j++;
                dp[i] = std::min(dp[i], costs[k] + dp[j]);
            }
        }
        return dp[0];
    }
};

// 解码方法
// 一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，消息不能分组为(1 11 06)，因为 "06" 不能映射为 "F"
// 这是由于 "6" 和 "06" 在映射中并不等价
// 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数
// 题目数据保证答案肯定是一个 32位 的整数
// 测试链接 : https://leetcode.cn/problems/decode-ways/
class DecodeWays {
    inline int f1(const std::string& s, int i)
    {
        if (i == s.size()) return 1;

        int ans;
        if (s[i] == '0') {
            ans = 0;
        }
        else {
            ans = f1(s, i + 1);
            if (i + 1 < s.size() && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) ans += f1(s, i + 2);
        }
        return ans;
    }

    inline int f2(const std::string& s, int i, int* dp)
    {
        if (i == s.size()) return 1;
        if (dp[i] != -1) return dp[i];
        int ans;
        if (s[i] == '0') {
            ans = 0;
        }
        else {
            ans = f2(s, i + 1, dp);
            if (i + 1 < s.size() && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26)
                ans += f2(s, i + 2, dp);
        }
        dp[i] = ans;
        return ans;
    }

public:
    // 暴力递归
    inline int numDecodings1(const std::string& s) { return f1(s, 0); }

    // 暴力尝试改记忆化搜索
    inline int numDecodings2(const std::string& s)
    {
        int* dp = new int[s.size()];
        std::fill(dp, dp + s.size(), -1);
        int ans = f2(s, 0, dp);
        delete[] dp;
        return ans;
    }

    // 严格位置依赖的动态规划
    inline int numDecodings3(const std::string& s)
    {
        int  n  = s.size();
        int* dp = new int[n + 1];
        dp[n]   = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            }
            else {
                dp[i] = dp[i + 1];
                if (i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) dp[i] += dp[i + 2];
            }
        }
        int ans = dp[0];
        delete[] dp;
        return ans;
    }

    // 严格位置依赖的动态规划 + 空间压缩
    inline int numDecodings4(const std::string& s)
    {
        int n = s.size();
        int a = 1, b = 0;
        for (int i = n - 1, cur; i >= 0; i--) {
            if (s[i] == '0') {
                cur = 0;
            }
            else {
                cur = a;
                if (i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) cur += b;
            }
            b = a;
            a = cur;
        }
        return a;
    }
};

// 解码方法 II
// 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 ：
// 'A' -> "1"
// 'B' -> "2"
// ...
// 'Z' -> "26"
// 要 解码 一条已编码的消息，所有的数字都必须分组
// 然后按原来的编码方案反向映射回字母（可能存在多种方式）
// 例如，"11106" 可以映射为："AAJF"、"KJF"
// 注意，像 (1 11 06) 这样的分组是无效的，"06"不可以映射为'F'
// 除了上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符
// 可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）
// 例如，"1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19"
// 对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息
// 给你一个字符串 s ，由数字和 '*' 字符
class DecodeWaysII {
    inline static constexpr long long MOD = 1e9 + 7;

    inline int f1(const std::string& s, int i)
    {
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;

        int ans = (s[i] == '*' ? 9 : 1) * f1(s, i + 1);
        if (i + 1 < s.size()) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) ans += f1(s, i + 2);
                }
                else {
                    if (s[i] == '1') ans += f1(s, i + 2) * 9;
                    if (s[i] == '2') ans += f1(s, i + 2) * 6;
                }
            }
            else {
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6')
                        ans += f1(s, i + 2) * 2;
                    else
                        ans += f1(s, i + 2);
                }
                else {
                    ans += f1(s, i + 2) * 15;
                }
            }
        }
        return ans;
    }

    inline long long f2(const std::string& s, int i, long long* dp)
    {
        if (i == s.size()) return 1;
        if (s[i] == '0') return 0;
        if (dp[i] != -1) return dp[i];

        long long ans = (s[i] == '*' ? 9 : 1) * f2(s, i + 1, dp);
        if (i + 1 < s.size()) {
            if (s[i] != '*') {
                if (s[i + 1] != '*') {
                    if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) ans += f2(s, i + 2, dp);
                }
                else {
                    if (s[i] == '1') ans += f2(s, i + 2, dp) * 9;
                    if (s[i] == '2') ans += f2(s, i + 2, dp) * 6;
                }
            }
            else {
                if (s[i + 1] != '*') {
                    if (s[i + 1] <= '6')
                        ans += f2(s, i + 2, dp) * 2;
                    else
                        ans += f2(s, i + 2, dp);
                }
                else {
                    ans += f2(s, i + 2, dp) * 15;
                }
            }
        }
        ans   = ans % MOD;
        dp[i] = ans;
        return ans;
    }

public:
    // 暴力递归，没有取模
    inline int numDecodings1(const std::string& s) { return f1(s, 0); }

    // 记忆化递归，取模
    inline int numDecodings2(const std::string& s)
    {
        int        n  = s.size();
        long long* dp = new long long[n];
        std::fill(dp, dp + n, -1);
        int ans = f2(s, 0, dp);
        delete[] dp;
        return ans;
    }

    // 严格位置依赖的动态规划
    inline int numDecodings3(const std::string& s)
    {
        int        n  = s.size();
        long long* dp = new long long[n + 1];
        std::fill(dp, dp + n + 1, 0);
        dp[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                dp[i] = (s[i] == '*' ? 9 : 1) * dp[i + 1];
                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) dp[i] += dp[i + 2];
                        }
                        else {
                            if (s[i] == '1') dp[i] += dp[i + 2] * 9;
                            if (s[i] == '2') dp[i] += dp[i + 2] * 6;
                        }
                    }
                    else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6')
                                dp[i] += dp[i + 2] * 2;
                            else
                                dp[i] += dp[i + 2];
                        }
                        else {
                            dp[i] += dp[i + 2] * 15;
                        }
                    }
                }
                dp[i] %= MOD;
            }
        }
        int ans = dp[0];
        delete[] dp;
        return ans;
    }

    // 严格位置依赖的动态规划 + 空间压缩
    inline int numDecodings4(const std::string& s)
    {
        long long a = 1, b = 0, cur = 0;
        int       n = s.size();
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] != '0') {
                cur = (s[i] == '*' ? 9 : 1) * a;
                if (i + 1 < n) {
                    if (s[i] != '*') {
                        if (s[i + 1] != '*') {
                            if ((s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) cur += b;
                        }
                        else {
                            if (s[i] == '1') cur += b * 9;
                            if (s[i] == '2') cur += b * 6;
                        }
                    }
                    else {
                        if (s[i + 1] != '*') {
                            if (s[i + 1] <= '6')
                                cur += b * 2;
                            else
                                cur += b;
                        }
                        else {
                            cur += b * 15;
                        }
                    }
                }
                cur %= MOD;
            }
            b   = a;
            a   = cur;
            cur = 0;
        }
        return (int)a;
    }
};

// 丑数 II
// 给你一个整数 n ，请你找出并返回第 n 个 丑数
// 丑数 就是只包含质因数 2、3 或 5 的正整数
// 测试链接 : https://leetcode.cn/problems/ugly-number-ii/
inline int nthUglyNumber(int n)
{
    if (n == 0) return -1;
    int* dp = new int[n];
    dp[0]   = 1;
    for (int i = 1, i2 = 0, i3 = 0, i5 = 0, a, b, c, cur; i < n; i++) {
        a     = dp[i2] * 2;
        b     = dp[i3] * 3;
        c     = dp[i5] * 5;
        cur   = std::min({a, b, c});
        dp[i] = cur;
        if (a == cur) i2++;
        if (b == cur) i3++;
        if (c == cur) i5++;
    }
    int ans = dp[n - 1];
    delete[] dp;
    return ans;
}

// 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
inline int longestValidParentheses(const std::string& s)
{
    int  n  = s.size();
    int* dp = new int[n];
    std::fill(dp, dp + n, 0);

    int ans = 0;
    for (int i = 1, pre; i < n; i++) {
        if (s[i] == '(') continue;
        pre = i - dp[i - 1] - 1;
        if (pre >= 0 && s[pre] == '(') dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
        ans = ans > dp[i] ? ans : dp[i];
    }
    delete[] dp;
    return ans;
}

// 环绕字符串中唯一的子字符串
// 定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串
// 所以 base 看起来是这样的：
// "..zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd.."
// 给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现
// 测试链接 : https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
inline int findSubstringInWraproundString(const std::string& str)
{
    int  n = str.size();
    int* s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = str[i] - 'a';
    }
    int* dp = new int[26];
    std::fill(dp, dp + 26, 0);
    dp[s[0]] = 1;
    for (int i = 1, cur, pre, len = 1; i < n; i++) {
        cur = s[i];
        pre = s[i - 1];
        if ((cur == 0 && pre == 25) || pre + 1 == cur)
            len++;
        else
            len = 1;
        dp[cur] = dp[cur] > len ? dp[cur] : len;
    }
    int ans = std::reduce(std::execution::par, dp, dp + 26);
    delete[] s;
    delete[] dp;
    return ans;
}

// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，答案对 1000000007 取模
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/
inline int distinctSubseqII(std::string s)
{
    constexpr int MOD = 1e9 + 7;
    int*          dp  = new int[26];
    std::fill(dp, dp + 26, 0);
    int all = 1, newAdd;
    for (char c : s) {
        newAdd      = (all - dp[c - 'a'] + MOD) % MOD;
        dp[c - 'a'] = (dp[c - 'a'] + newAdd) % MOD;
        all         = (all + newAdd) % MOD;
    }
    return (all - 1 + MOD) % MOD;
}
}   // namespace lxj

#endif